package com.dbh.alg.datastructure;

/**
 * 合并两个有序链表
 * @author 董帮辉
 * @date 2025/5/10
 **/
public class E06Leetcode21 {

    public static ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        ListNode s = new ListNode(-1, null);
        ListNode p = s;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
               p.next = p1;
               p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return s.next;
    }

    /**
     * 合并两个有序链表-递归方式
     * @param p1 链表1
     * @param p2 链表2
     * @return 合并后的链表
     */
    public static ListNode mergeTwoLists2(ListNode p1, ListNode p2) {
        if (p1 == null) {
            return p2;
        }
        if (p2 == null) {
            return p1;
        }
        if (p1.val < p2.val) {
            p1.next = mergeTwoLists(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeTwoLists(p1, p2.next);
            return p2;
        }
    }


    public static void main(String[] args) {
        ListNode p1 = ListNode.of(1, 2, 4, 5);
        ListNode p2 = ListNode.of(2, 6, 8, 9);
        System.out.println(mergeTwoLists2(p1, p2));

    }
}
